using System;
using System.Collections.Generic;
using System.Text;

namespace COME342.CollisionResolution.BinaryTree
{
    public class AVLTree<T> : BinaryTreeADT<T> where T : IComparable
    {
        public AVLTree<T> left = null;
        public AVLTree<T> right = null;
        public AVLTree<T> parent = null;

        public delegate void PreRotationHandler(AVLTree<T> tree, T data, RotationType rot);
        public delegate void PostBalanceHandler(AVLTree<T> tree, T data);
        
        public static event PreRotationHandler PreRotation;
        public static event PostBalanceHandler PostBalance;
        
        public enum RotationType
        {
            LL,
            LR,
            RR,
            RL
        }

        protected virtual void OnPostBalance(T data)
        {
            if (PostBalance != null)
                PostBalance(this.GetRoot(), data);
        }

        protected virtual void OnPreRotation(T data, RotationType rot)
        {
            if (PreRotation != null)
                PreRotation(this.GetRoot(), data, rot);
        }

        public AVLTree<T> GetRoot()
        {
            AVLTree<T> bt;
            bt = this;
            while (!bt.IsRoot())
                bt = bt.parent;
            return bt;        
        }

        public class Node<T>
        {
            public T Data;
            public int Height;
            public int BalanceFactor;
            public int Breadth;

            public Node(T d, int h, int bf, int b)
            {
                Data = d;
                Height = h;
                BalanceFactor = bf;
                Breadth = b;
            }
        }

        public int height = 0;
        private int BalanceFactor = 0;

        public bool IsBalanced
        {
            get { return BalanceFactor * BalanceFactor <= 1; }            
        }

        private AVLTree()
        {
            height = 0;
            BalanceFactor = 0;
        }

        public AVLTree(T data)
        {
            this.data = data;
            height = 0;
            BalanceFactor = 0;
            left = new AVLTree<T>();
            right = new AVLTree<T>();
        }        

        public AVLTree<T> Copy()
        {
            AVLTree<T> ret = new AVLTree<T>(data);

            Queue<AVLTree<T>> breadth = new Queue<AVLTree<T>>();
            breadth.Enqueue(this);
            AVLTree<T> tmp;
            while (breadth.Count > 0)
            {
                tmp = breadth.Dequeue();
                ret.BinaryInsert(tmp.data);

                if (tmp.left != null && tmp.left.data != null)
                    breadth.Enqueue(tmp.left);
                if (tmp.right != null && tmp.right.data != null)
                    breadth.Enqueue(tmp.right);
            }

            /*AVLTree<T>.PreBalance = PreBalance;
            AVLTree<T>.PostRRRotation = PostRRRotation;
            AVLTree<T>.PostLLRotation = PostLLRotation;
            AVLTree<T>.PostBalance = PostBalance;*/

            return ret;
        }

        public List<Node<T>> BreadthFirst()
        {
            List<Node<T>> ret = new List<Node<T>>();

            Queue<AVLTree<T>> breadth = new Queue<AVLTree<T>>();
            int b = 0;
            breadth.Enqueue(this);
            AVLTree<T> tmp;
            AVLTree<T> t;
            while (breadth.Count > 0)
            {
                tmp = breadth.Dequeue();
                b=0;
                t = tmp;
                while(!t.IsRoot())
                {
                    t = t.parent;
                    b++;
                }
                    
                ret.Add(new Node<T>(tmp.data, tmp.height, tmp.BalanceFactor, b));

                if (tmp.left != null && tmp.left.data != null)
                    breadth.Enqueue(tmp.left);
                if (tmp.right != null && tmp.right.data != null)
                    breadth.Enqueue(tmp.right);
            }

            return ret;
        }

        public void Insert(T data)
        {            
            if (this.data == null)
            {
                this.data = data;
                return;
            }

            if (this.data.CompareTo(data) > 0)
            {
                if (this.left != null)
                    this.left.Insert(data);
                else
                    this.left = new AVLTree<T>(data);
            }
            else if (this.data.CompareTo(data) < 0)
            {
                if (this.right != null)
                    this.right.Insert(data);
                else
                    this.right = new AVLTree<T>(data);
            }
            
            Balance();            
        }

        //to be used in Copy operation only!!
        private void BinaryInsert(T data)
        {
            if (data == null)
                return;

            if (this.data == null)
            {
                this.data = data;
                return;
            }

            if (this.data.CompareTo(data) > 0)
            {
                if (this.left != null)
                    this.left.BinaryInsert(data);
                else
                    AddToLeft(data);
            }
            else if (this.data.CompareTo(data) < 0)
            {
                if (this.right != null)
                    this.right.BinaryInsert(data);
                else
                    AddToRight(data);
            }
        }

        protected void Balance()
        {
            AdjustHeight();

            //fix parent relationships
            Queue<AVLTree<T>> breadth = new Queue<AVLTree<T>>();
            breadth.Enqueue(this);
            AVLTree<T> tmp;
            while (breadth.Count > 0)
            {
                tmp = breadth.Dequeue();

                if (tmp.left != null && tmp.left.data != null)
                {
                    breadth.Enqueue(tmp.left);
                    tmp.left.parent = tmp;
                }
                if (tmp.right != null && tmp.right.data != null)
                {
                    breadth.Enqueue(tmp.right);
                    tmp.right.parent = tmp;
                }
                tmp.AdjustHeight();
            }// not necessary only for demonstration purposes on frmTree.cs            

            if (BalanceFactor > 1)
            {
                if (left != null && left.BalanceFactor > 0)
                {
                    OnPreRotation(data, RotationType.LL);
                    LLRotation();
                }
                else
                {
                    OnPreRotation(data, RotationType.LR);
                    LRRotation();
                }
            }
            else if (BalanceFactor < -1)
            {
                if (right != null && right.BalanceFactor < 0)
                {
                    OnPreRotation(data, RotationType.RR);
                    RRRotation();
                }
                else
                {
                    OnPreRotation(data, RotationType.RL);
                    RLRotation();
                }
            }

            //fix parent relationships
            breadth = new Queue<AVLTree<T>>();
            breadth.Enqueue(this);            
            while (breadth.Count > 0)
            {
                tmp = breadth.Dequeue();

                if (tmp.left != null && tmp.left.data != null)
                {
                    breadth.Enqueue(tmp.left);
                    tmp.left.parent = tmp;
                }
                if (tmp.right != null && tmp.right.data != null)
                {
                    breadth.Enqueue(tmp.right);
                    tmp.right.parent = tmp;
                }
                tmp.AdjustHeight();
            }

            OnPostBalance(data);
        }

        protected void LLRotation()
        {            
            if (IsEmpty())
                throw new InvalidOperationException();

            if (right == null)
                right = new AVLTree<T>();
            AVLTree<T> tmp = right.Copy();
            right = left.Copy();
            left = right.left.Copy();
            right.left = right.right.Copy();
            right.right = tmp;
            
            T t = data;
            data = right.data;
            right.data = t;

            right.AdjustHeight();
            AdjustHeight();
        }

        protected void RRRotation()
        {
            if (IsEmpty())
                throw new InvalidOperationException();

            if (left == null)
                left = new AVLTree<T>();
            AVLTree<T> tmp = left.Copy();
            left = right.Copy();
            right = left.right.Copy();
            left.right = left.left.Copy();
            left.left = tmp;

            T t = data;
            data = left.data;
            left.data = t;

            left.AdjustHeight();
            AdjustHeight();            
        }

        protected void LRRotation()
        {
            if (IsEmpty())
                throw new InvalidOperationException();
            left.RRRotation();
            LLRotation();
        }

        protected void RLRotation()
        {
            if (IsEmpty())
                throw new InvalidOperationException();
            right.LLRotation();
            RRRotation();
        }

        public AVLTree<T> FindNode(T data)
        {            
            if (this.data.CompareTo(data) == 0)
                return this;
            
            AVLTree<T> ret;

            if (!IsLeftEmpty())
            {
                ret = left.FindNode(data);
            if (ret != null)
                return ret;
            }
            if (!IsRightEmpty())
            {
                ret = right.FindNode(data);
                if (ret != null)
                    return ret;
            }
            return null;
        }

        public override bool IsRoot()
        {
            return parent == null;
        }

        public override bool IsLeaf()
        {
            return left == null && right == null;
        }

        public override bool IsLeftEmpty()
        {
            return left == null || left.data == null;
        }

        public override bool IsRightEmpty()
        {
            return right == null || right.data == null;
        }

        public bool IsEmpty()
        {
            return IsLeftEmpty() && IsRightEmpty();
        }

        private void PreorderTraverse(ref List<T> ret)
        {
            ret.Add(data);
            if (left != null && left.data != null)
                left.PreorderTraverse(ref ret);
            if (right != null && right.data != null)
                right.PreorderTraverse(ref ret);
        }

        public override List<T> PreOrderTraverse()
        {
            List<T> ret = new List<T>();
            PreorderTraverse(ref ret);
            return ret;
        }

        public override List<T> InOrderTraverse()
        {
            List<T> ret = new List<T>();
            InOrderTraverse(ref ret);
            return ret;
        }

        private void InOrderTraverse(ref List<T> ret)
        {
            if (left != null && left.data != null)
                left.InOrderTraverse(ref ret);
            ret.Add(data);
            if (right != null && right.data != null)
                right.InOrderTraverse(ref ret);
        }

        public override List<T> PostOrderTraverse()
        {
            List<T> ret = new List<T>();
            PostOrderTraverse(ref ret);
            return ret;
        }

        private void PostOrderTraverse(ref List<T> ret)
        {
            if (left != null && left.data != null)
                left.PostOrderTraverse(ref ret);
            if (right != null && right.data != null)
                right.PostOrderTraverse(ref ret);
            ret.Add(data);
        }

        private void AddToLeft(T data)
        {
            if (left != null)
                throw new ArgumentException("Left subtree is not null. Can not insert.");
            left = new AVLTree<T>(data);
            left.parent = this;
            AdjustHeight();
        }

        private void AdjustHeight()
        {
            if (IsEmpty())
            {
                height = 0;
                return;
            }
            
            if (IsLeftEmpty())
            {
                height = right.height + 1;
                BalanceFactor = 0 - height;
            }
            else if (IsRightEmpty())
            {
                height = left.height + 1;
                BalanceFactor = height - 0;
            }
            else
            {
                height = 1 + (left.height > right.height ? left.height : right.height);
                BalanceFactor =  left.height - right.height;
            }           

            if (parent != null)
                parent.AdjustHeight();
        }

        private void AddToRight(T data)
        {
            if (right != null)
                throw new ArgumentException("Right subtree is not null. Can not insert.");
            right = new AVLTree<T>(data);
            right.parent = this;
            AdjustHeight();
        }

        public override string ToString()
        {
            return data.ToString()
                + " h: " + height.ToString()
                + " bf: " + BalanceFactor.ToString();
                /*+ " L:" + (IsLeftEmpty() ? "-" : left.data.ToString()) 
                + " R:" + (IsRightEmpty() ? "-" : right.data.ToString());*/
        }
    }
}